package com.leetcode.BinaryTree;

//路径总和
public class lc_437 {
    int t, ans;
    public int pathSum(TreeNode root, int targetSum) {
        t = targetSum;
        if (root == null)  return 0;
        dfs1(root);
        return ans;
    }

    //使用dfs1遍历每一个节点 使用dfs2得到该节点为起点的路径数目
    private void dfs1(TreeNode root) {
        //边界条件: 当遍历完节点之后,直接return
        if(root == null) return;
        dfs2(root, root.val);
        dfs1(root.left);
        dfs1(root.right);
    }

    private void dfs2(TreeNode root, long val) {
        if(val == t) ans++;
        if(root.left != null) dfs2(root.left, val + root.left.val);
        if(root.right != null) dfs2(root.right, val + root.right.val);
    }
}
